package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Code25_PathWithMaximumProbability {
	public static class Node {
		public int value;
		public int in;
		public int out;
		public ArrayList<Node> nexts;
		public ArrayList<Edge> edges;

		public Node(int value) {
			this.value = value;
			in = 0;
			out = 0;
			nexts = new ArrayList<>();
			edges = new ArrayList<>();
		}
	}

	public static class Graph {
		public HashMap<Integer, Node> nodes;
		public HashSet<Edge> edges;

		public Graph() {
			nodes = new HashMap<>();
			edges = new HashSet<>();
		}
	}

	public static class Edge {
		public int weight;
		public Node from;
		public Node to;

		public Edge(int weight, Node from, Node to) {
			this.weight = weight;
			this.from = from;
			this.to = to;
		}
	}

	public static Graph createGraph(int[][] matrix) {
		Graph graph = new Graph();

		for (int i = 0; i < matrix.length; i++) {
			Integer from = matrix[i][0];
			Integer to = matrix[i][1];
			Integer weight = matrix[i][2];

			if (!graph.nodes.containsKey(from)) {
				graph.nodes.put(from, new Node(from));
			}
			if (!graph.nodes.containsKey(to)) {
				graph.nodes.put(to, new Node(to));
			}

			Node fromNode = graph.nodes.get(from);
			Node toNode = graph.nodes.get(to);

			Edge newEdge = new Edge(weight, fromNode, toNode);
			fromNode.nexts.add(toNode);
			fromNode.out++;
			toNode.in++;

			fromNode.edges.add(newEdge);
			graph.edges.add(newEdge);
		}

		return graph;
	}

	public static class NodeRecord {
		public Node node;
		public double distance;

		public NodeRecord(Node node, double distance) {
			this.node = node;
			this.distance = distance;
		}
	}

	public static class NodeHeap {
		private Node[] nodes;
		private HashMap<Node, Integer> heapIndexMap;
		private HashMap<Node, Double> distanceMap;
		private int size;

		public NodeHeap(int size) {
			nodes = new Node[size];
			heapIndexMap = new HashMap<>();
			distanceMap = new HashMap<>();
			this.size = 0;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public void addOrUpdateOrIgnore(Node node, double distance) {
			if (inHeap(node)) {
				distanceMap.put(node, Math.max(distanceMap.get(node), distance));
				insertHeapify(node, heapIndexMap.get(node));
			}
			if (!isEntered(node)) {
				nodes[size] = node;
				heapIndexMap.put(node, size);
				distanceMap.put(node, distance);
				insertHeapify(node, size++);
			}
		}

		public NodeRecord pop() {
			NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
			swap(0, size - 1);
			heapIndexMap.put(nodes[size - 1], -1);
			distanceMap.remove(nodes[size - 1]);
			nodes[size - 1] = null;
			heapify(0, --size);
			return nodeRecord;
		}

		private void insertHeapify(Node node, int index) {
			while (distanceMap.get(nodes[index]) > distanceMap.get(nodes[(index - 1) / 2])) {
				swap(index, (index - 1) / 2);
				index = (index - 1) / 2;
			}
		}

		private void heapify(int index, int size) {
			int left = index * 2 + 1;
			while (left < size) {
				int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) > distanceMap.get(nodes[left])
						? left + 1
						: left;
				smallest = distanceMap.get(nodes[smallest]) > distanceMap.get(nodes[index]) ? smallest : index;
				if (smallest == index) {
					break;
				}
				swap(smallest, index);
				index = smallest;
				left = index * 2 + 1;
			}
		}

		private boolean isEntered(Node node) {
			return heapIndexMap.containsKey(node);
		}

		private boolean inHeap(Node node) {
			return isEntered(node) && heapIndexMap.get(node) != -1;
		}

		private void swap(int index1, int index2) {
			heapIndexMap.put(nodes[index1], index2);
			heapIndexMap.put(nodes[index2], index1);
			Node tmp = nodes[index1];
			nodes[index1] = nodes[index2];
			nodes[index2] = tmp;
		}
	}

	public static HashMap<Node, Double> dijkstra2(Node head, int size, Map<Integer, Double> doubleMap) {
		HashMap<Node, Double> result = new HashMap<>();
		if (head == null) {
			result.put(head, 0.0);
			return result;
		}

		NodeHeap nodeHeap = new NodeHeap(size);
		nodeHeap.addOrUpdateOrIgnore(head, 1.0);

		while (!nodeHeap.isEmpty()) {
			NodeRecord record = nodeHeap.pop();
			Node cur = record.node;
			double distance = record.distance;

			if (cur != null) {
				for (Edge edge : cur.edges) {
					nodeHeap.addOrUpdateOrIgnore(edge.to, doubleMap.get(edge.weight) * distance);
				}
			}

			result.put(cur, distance);
		}
		return result;
	}

	public static double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
		int[][] matrix = new int[edges.length * 2][3];
		Map<Integer, Double> doubleMap = new HashMap<>();

		int j = 0;
		for (int i = 0; i < edges.length; i++) {
			int from = edges[i][0];
			int to = edges[i][1];
			doubleMap.put(i, succProb[i]);
			int weight = i;

			int[] temp = new int[3];
			temp[0] = from;
			temp[1] = to;
			temp[2] = weight;

			matrix[j++] = temp;
		}

		for (int i = 0; i < edges.length; i++) {
			int from = edges[i][1];
			int to = edges[i][0];
			doubleMap.put(i, succProb[i]);
			int weight = i;

			int[] temp = new int[3];
			temp[0] = from;
			temp[1] = to;
			temp[2] = weight;

			matrix[j++] = temp;
		}

		Graph graph = createGraph(matrix);

		Node head = graph.nodes.get(start);
		if (head == null) {
			return 0.0000;
		}

		HashMap<Node, Double> disMap = dijkstra2(head, n, doubleMap);

		Node endNode = graph.nodes.get(end);
		return disMap.get(endNode) != null ? disMap.get(endNode) : 0.00000;
	}
}
